import collections


class Solution(object):
    def numberWays(self, hats):
        d = collections.defaultdict(set)
        for index, hat in enumerate(hats):
            for u in hat:
                d[u].add(index)
        n = len(hats)
        st = [0] * (1 << n)
        st[0] = 1
        ans = 0
        base = 10 ** 9 + 7
        for i in range(1, 41):
            next_st = [0] * (1 << n)
            for val in range(1 << n):
                next_st[val] += st[val]
                for u in d[i]:
                    if (val >> u) & 1 == 0:
                        next_val = val | (1 << u)
                        if next_val == (2 ** n - 1):
                            ans = (ans + st[val]) % base
                        else:
                            next_st[next_val] = (next_st[next_val] + st[val]) % base
            st = next_st
        return ans


data = Solution()
hats = [[3,5,1],[3,5]]
print(data.numberWays(hats))
